package com.lw.leetcode.sort.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 1942. 最小未被占据椅子的编号
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/28 17:56
 */
public class SmallestChair {

    public static void main(String[] args) {
        SmallestChair test = new SmallestChair();

        // 1
//        int[][] times = {{1, 4}, {2, 3}, {4, 6}};
//        int targetFriend = 1;

        // 2
        int[][] times =  {{3,10},{1,5},{2,6}};
        int targetFriend = 0;

        // 2
//        int[][] times =  {{33889,98676},{80071,89737},{44118,52565},{52992,84310},{78492,88209},{21695,67063},{84622,95452},{98048,98856},{98411,99433},{55333,56548},{65375,88566},{55011,62821},{48548,48656},{87396,94825},{55273,81868},{75629,91467}};
//        int targetFriend = 6;

        int i = test.smallestChair(times, targetFriend);
        System.out.println(i);
    }

    public int smallestChair(int[][] times, int targetFriend) {
        int t = times[targetFriend][0];
        Arrays.sort(times, (a, b) -> Integer.compare(a[0], b[0]));
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        TreeMap<Integer, Integer> map = new TreeMap<>();
        Map<Integer, List<Integer>> items = new HashMap<>();
        for (int[] time : times) {
            int a = time[0];
            while (!queue.isEmpty() && queue.peek() <= a) {
                find(map, items, queue.poll());
            }
            Integer key = map.get(0);
            if (key == null) {
                key = -1;
            }
            if (map.get(key + 2) == null) {
                map.put(0, key + 1);
            } else {
                map.put(0, map.get(key + 2));
                map.remove(key + 2);
            }
            items.computeIfAbsent(time[1], v -> new ArrayList<>()).add(key + 1);
            queue.add(time[1]);
            if (t == time[0]) {
                return key  + 1;
            }
        }
        return -1;
    }

    private void find (TreeMap<Integer, Integer> map, Map<Integer, List<Integer>> items, int k) {
        List<Integer> list = items.get(k);
        items.put(k, null);
        if (list != null) {
            for (int v : list) {
                int key = map.floorKey(v);
                int value = map.get(key);
                if (key == v) {
                    map.remove(key);
                    if (value != key) {
                        map.put(key + 1, value);
                    }
                } else if (v == value) {
                    map.put(key, v - 1);
                }  else {
                    map.put(key, v - 1);
                    map.put(v + 1, value);
                }
            }
        }
    }

}
